//--------------------------------------------------------------------
//
//  Laboratory 4                                           ordlist.cpp
//
//  Class implementation for the array implementation of the Ordered
//  List ADT -- inherits the array implementation of the List ADT
//  (Laboratory 3)
//
//--------------------------------------------------------------------

#ifndef ORDLIST_CPP
#define ORDLIST_CPP

#include "ordlist.h"
#include <stdexcept>
#include <iostream>

    // Constructor
    template < class DT >
    OrdList<DT>::OrdList( int maxNumber ):aList<DT> (maxNumber){
/*    	if (maxNumber > defMaxListSize){
    		throw bad_alloc();
    	} else{
    	    size=0;
    	    cursor=-1;
    	    maxSize = maxNumber;
    	    dataItems = new DataType[maxSize];
        }
*/    }

    // Modified (or new) list manipulation operations
    //Prelab
    template < class DT >
    void OrdList<DT>::insert ( const DT &newDataItem ){
    	if (isFull()){
            throw logic_error("List Full!");
    	} else if(isEmpty()) {
    	    dataItems[0]=newDataItem;
    	    size++;
    	    cursor=0;
    	} else {
    	    int searchKey = newDataItem.getKey();
    	    binarySearch(searchKey, cursor);
    	    aList<DT>::insert(newDataItem);
        }
    }
    //Prelab
    template < class DT >
    void OrdList<DT>::replace ( const DT &newDataItem ){
    	if (isEmpty()){
            throw logic_error("List Empty!");
    	} else{
    	    aList<DT>::remove();
    	    insert(newDataItem);
        }
    }
    
    //Prelab
    template < class DT >
    bool OrdList<DT>::retrieve ( int searchKey, DT *&searchDataItem ){
    	if (isEmpty()){
            throw logic_error("List Empty!");
    	} else{
    	    int tmpindex;
    	    if (binarySearch(searchKey,tmpindex)){
    	    	cursor = tmpindex;
    	    	searchDataItem = &dataItems[cursor];
    	    	return true;
    	    } else return false;   	    	
        }
    }
    
    // Output the list structure -- used in testing/debugging
    //void showStructure () const;

    // Locates an element (or where it should be) based on its key
    //bool OrdList::binarySearch ( char searchKey, int &index );
template < class DT >
bool OrdList<DT>::binarySearch ( int searchKey, int &index )

// Binary search routine. Searches a list for the data item with
// key searchKey. If the data item is found, then returns true with
// index returning the array index of the entry containing searchKey.
// Otherwise, returns false with index returning the array index of the
// entry containing the largest key that is smaller than searchKey
// (or -1 if there is no such key).

{
    int low  = 0,           // Low index of current search range
        high = size - 1;    // High index of current search range
    bool result;            // Result returned

    while ( low <= high )
    {
        index = ( low + high ) / 2;               // Compute midpoint
        if ( searchKey < dataItems[index].getKey() )
           high = index - 1;                      // Search lower half
        else if ( searchKey > dataItems[index].getKey() )
           low = index + 1;                       // Search upper half
        else
           break;                                 // searchKey found
    }

    if ( low <= high )
       result = true;       // searchKey found
       //return true;
    else
    {
       index = high;        // searchKey not found, adjust index
       result = false;
       //return false;
    }

    return result;
}

#endif // #ifndef ORDLIST_CPP

